home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 3 / Cream of the Crop 3.iso / comm / wnos5src.zip / LZW.C < prev    next >
Text File  |  1993-10-19  |  15KB  |  607 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV.
  6.  * Permission granted for non-commercial distribution only.
  7.  */
  8.  
  9. #include "global.h"
  10. #include "config.h"
  11. #ifdef LZW
  12. #include "mbuf.h"
  13. #include "proc.h"
  14. #include "lzw.h"
  15. #include "usock.h"
  16. #include "session.h"
  17. #include "cmdparse.h"
  18. #include <ctype.h>
  19.  
  20. static void near fastencode __ARGS((struct usock *up,char data));
  21. static void near morebits __ARGS((struct lzw *lzw));
  22. static void near cleartbl __ARGS((struct lzw *lzw));
  23. static void near addtobuffer __ARGS((struct usock *up,int32 code));
  24. static void near decodetbl __ARGS((int32 code,struct lzw *lzw));
  25. static int32 near nextcode __ARGS((struct usock *up));
  26.  
  27. int
  28. dolzw(int argc,char **argv,void *p)
  29. {
  30.     switch(*argv[1]) {
  31.     case 'm':
  32.         if(argc == 2) {
  33.             tprintf("LZW mode: %s\n",Lzwmode ? "fast" : "compact");
  34.             return 0;
  35.         } else {
  36.             switch(*argv[2]) {
  37.             case 'f':
  38.                 Lzwmode = LZWFAST;
  39.                 return 0;
  40.             case 'c':
  41.                 Lzwmode = LZWCOMPACT;
  42.                 return 0;
  43.             default:
  44.                 tputs("Usage: lzw mode <fast|compact>\n");
  45.                 return -1;
  46.             }
  47.         }
  48.     case 'b':
  49.         return setintrc(&Lzwbits,"LZW bits",--argc,++argv,9,16);
  50.     case '+':
  51.         if(argc == 3) {
  52.             struct session *sp;
  53.             if((sp = sessptr(argv[2])) != NULLSESSION) {
  54.                 lzwinit(sp->s,Lzwbits,Lzwmode);
  55.             }
  56.         }
  57.         return 0;
  58.     }
  59.     return -1;
  60. }
  61.  
  62. /* Initialize a socket for compression. Bits specifies the maximum number
  63.  * of bits per codeword. The input and output code tables might grow to
  64.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  65.  * recommendation for the decoding, the actual number of bits may be
  66.  * larger, but not never more than 16.
  67.  */
  68. void
  69. lzwinit(
  70. int s,        /* socket to operate on */
  71. int bits,    /* maximum number of bits per codeword */
  72. int mode)    /* compression mode, LZWCOMPACT or LZWFAST */
  73. {
  74.     struct usock *up;
  75.  
  76.     if((up = itop(s)) == NULLUSOCK) {
  77.         return;
  78.     }
  79.     up->zout = mxallocw(sizeof(struct lzw));
  80.     up->zin = mxallocw(sizeof(struct lzw));
  81.     up->zout->codebits = LZWBITS;
  82.  
  83.     if(bits < LZWBITS) {
  84.         up->zout->maxbits = LZWBITS;
  85.     }
  86.     if(bits > 16 || bits == 0) {
  87.         up->zout->maxbits = 16;
  88.     }
  89.     if(bits >= LZWBITS && bits <= 16) {
  90.         up->zout->maxbits = bits;
  91.     }
  92.     up->zout->nextbit = 0;
  93.     up->zout->prefix = -1;
  94.     up->zout->version = -1;
  95.     up->zout->code = -1;
  96.     up->zout->mode = (mode & 1);    /* only the last bit is significant */
  97.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  98.  
  99.     up->zin->codebits = LZWBITS;
  100.     up->zin->maxbits = -1;
  101.     up->zin->nextbit = 0;
  102.     up->zin->prefix = -1;
  103.     up->zin->version = -1;
  104.     up->zin->code = -1;
  105.     up->zin->mode = LZWCOMPACT;
  106.     up->zin->next = ZFLUSH + 1;
  107.     up->zin->buf = NULLBUF;
  108. }
  109.  
  110. void
  111. lzwfree(struct usock *up)
  112. {
  113.     if(up->zout != NULLLZW) {
  114.         cleartbl(up->zout);
  115.         xfree(up->zout);
  116.         up->zout = NULLLZW;
  117.     }
  118.     if(up->zin != NULLLZW) {
  119.         cleartbl(up->zin);
  120.         free_q(&up->zin->buf);
  121.         xfree(up->zin);
  122.         up->zin = NULLLZW;
  123.     }
  124. }
  125. /* LZW encoding routine.
  126.  * See if the string specified by code + data is in the string table. If so,
  127.  * set prefix equal to the code of that string. Otherwise insert code + data
  128.  * in the string and set prefix equal to data.
  129.  */
  130. void
  131. lzwencode(int s,char data)
  132. {
  133.     struct usock *up;
  134.     struct lzw *lzw;
  135.     int32 code, pagelim;
  136.     unsigned int i,j;
  137.  
  138.     if((up = itop(s)) == NULLUSOCK) {
  139.         return;
  140.     }
  141.     lzw = up->zout;
  142.     code = up->zout->prefix;
  143.  
  144.     /* the first byte sent will be the version number */
  145.     if(lzw->version == -1) {
  146.         lzw->version = ZVERSION;
  147.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  148.         /* then send our recommended maximum number of codebits */
  149.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  150.     }
  151.     lzw->cnt++;
  152.  
  153.     if(code == -1) {
  154.         lzw->prefix = (int32)uchar(data);
  155.         return;
  156.     }
  157.     if(lzw->mode == LZWFAST) {
  158.         fastencode(up,data);
  159.         return;
  160.     }
  161.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  162.  
  163.     if(code <= ZFLUSH) {
  164.         i = j = 0;
  165.     } else {
  166.         i = (unsigned int)((code - ZFLUSH) / LZWBLK);
  167.         j = (unsigned int)((code - ZFLUSH) % LZWBLK);
  168.     }
  169.     if(lzw->tu.tbl == NULL) {
  170.         lzw->tu.tbl = cxallocw((unsigned)pagelim,sizeof(struct zentry *));
  171.     }
  172.     for(;;) {
  173.         if(itop(s) == NULLUSOCK) {        /* the connection has been closed */
  174.             return;
  175.         }
  176.         if(up->zout == NULLLZW) {         /* ...or is about to be closed */
  177.             return;
  178.         }
  179.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  180.             lzw->tu.tbl[i] = cxallocw(LZWBLK,sizeof(struct zentry));
  181.             memset(lzw->tu.tbl[i],0xff,LZWBLK * sizeof(struct zentry));
  182.         }
  183.         while(j < LZWBLK) {
  184.             if(lzw->tu.tbl[i][j].data == data
  185.               && lzw->tu.tbl[i][j].code == (int16)code) {
  186.                 lzw->prefix = (int32)(i * LZWBLK + j + ZFLUSH + 1);
  187.                 return;
  188.             }
  189.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  190.                 lzw->tu.tbl[i][j].code = (int16)code;
  191.                 lzw->tu.tbl[i][j].data = data;
  192.                 addtobuffer(up,code);
  193.                 lzw->prefix = (int32) uchar(data);
  194.                 lzw->next++;
  195.  
  196.                 if(lzw->next ==    (int32) (1 << lzw->codebits)) {
  197.                     /* the current table is now full */
  198.                     morebits(lzw);
  199.                 }
  200.                 if(lzw->next + 1 == (int32) (1 << lzw->maxbits)) {
  201.                     /* The last codeword has been reached.
  202.                      * (Or last - 1.) Signal this and start all
  203.                      * over again.
  204.                      */
  205.                     addtobuffer(up,lzw->prefix);
  206.  
  207.                     if(lzw->next + 1 == (int32) (1 << lzw->codebits)) {
  208.                         morebits(lzw);
  209.                     }
  210.                     addtobuffer(up,ZCC);
  211.                     cleartbl(lzw);
  212.                 }
  213.                 return;
  214.             }
  215.             ++j;
  216.         }
  217.         pwait(NULL);
  218.         ++i;
  219.         j = 0;
  220.     }
  221. }
  222.  
  223. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  224.  * bytes.
  225.  */
  226. static void near
  227. fastencode(struct usock *up,char data)
  228. {
  229.     struct zfast *z;
  230.     struct mbuf *bp;
  231.     int16 cnt, h;
  232.     struct lzw *lzw = up->zout;
  233.     int32 code = up->zout->prefix;
  234.  
  235.     if(lzw->tu.bpp == NULLBUFP) {
  236.         lzw->tu.bpp = cxallocw(ZHASH,sizeof(struct mbuf *));
  237.     }
  238.     h = lobyte(code);
  239.     h ^= hibyte(code);
  240.     h ^= data;
  241.     h = h % ZHASH;
  242.  
  243.     if(lzw->tu.bpp[h] == NULLBUF) {
  244.         lzw->tu.bpp[h] = alloc_mbuf(LZWBLK);
  245.     }
  246.     bp = lzw->tu.bpp[h];
  247.     cnt = bp->cnt / sizeof(struct zfast);
  248.     z = (struct zfast *) bp->data;
  249.  
  250.     while(cnt > 0) {
  251.         if(z->data == data && z->code == (int16)code) {
  252.             lzw->prefix = (int32) z->owncode;
  253.             return;
  254.         }
  255.         z++;
  256.         if(--cnt == 0) {
  257.             if(bp->next == NULLBUF) {
  258.                 break;
  259.             }
  260.             bp = bp->next;
  261.             cnt = bp->cnt / sizeof(struct zfast);
  262.             z = (struct zfast *) bp->data;
  263.         }
  264.     }
  265.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  266.         z = (struct zfast *) &bp->data[bp->cnt];
  267.         bp->cnt += sizeof(struct zfast);
  268.     } else {
  269.         bp->next = alloc_mbuf(LZWBLK);
  270.         z = (struct zfast *) bp->next->data;
  271.         bp->next->cnt = sizeof(struct zfast);
  272.     }
  273.     z->code = (int16)code;
  274.     z->data = data;
  275.     z->owncode = (int16)lzw->next++;
  276.     addtobuffer(up,code);
  277.     lzw->prefix = (int32) uchar(data);
  278.  
  279.     if(lzw->next == (int32) (1 << lzw->codebits)) {
  280.         /* Increase the number of bits per codeword */
  281.         morebits(lzw);
  282.     }
  283.     if(lzw->next + 1 == (int32) (1 << lzw->maxbits)) {
  284.         /* The last codeword has been reached. (Or last - 1.)
  285.          * Signal this and start all over again.
  286.          */
  287.         addtobuffer(up,lzw->prefix);
  288.  
  289.         if(lzw->next + 1 == (int32) (1 << lzw->codebits)) {
  290.             morebits(lzw);
  291.         }
  292.         addtobuffer(up,ZCC);
  293.         cleartbl(lzw);
  294.     }
  295.     pwait(NULL);
  296. }
  297.  
  298. /* increase the number of significant bits in the codewords, and increase
  299.  * the size of the string table accordingly.
  300.  */
  301. static void near
  302. morebits(struct lzw *lzw)
  303. {
  304.  
  305.     lzw->codebits++;
  306.  
  307.     if(lzw->mode != LZWFAST) {
  308.         int32 oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  309.         int32 pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  310.  
  311.         struct zentry **newt = cxallocw((int)pagelim,sizeof(struct zentry *));
  312.         memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * (int)oldp);
  313.         xfree(lzw->tu.tbl);
  314.         lzw->tu.tbl = newt;
  315.     }
  316. }
  317.  
  318. static void near
  319. cleartbl(struct lzw *lzw)
  320. {
  321.     int32 i;
  322.  
  323.     lzw->codebits = LZWBITS;
  324.     lzw->prefix = -1;
  325.     lzw->next = ZFLUSH + 1;
  326.  
  327.     if(lzw->tu.p == NULL) {
  328.         return;
  329.     }
  330.     if(lzw->mode == LZWCOMPACT) {
  331.         int32 pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  332.  
  333.         for(i = 0; i < pagelim; ++i) {
  334.             xfree(lzw->tu.tbl[(int)i]);
  335.         }
  336.     } else {
  337.         for(i = 0; i < ZHASH; ++i) {
  338.             free_p(lzw->tu.bpp[(int)i]);
  339.         }
  340.     }
  341.     xfree(lzw->tu.p);
  342.     lzw->tu.p = NULL;
  343. }
  344.  
  345. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  346.  * code stream should be written first. The codeword ZFLUSH is used to
  347.  * pad the buffer to a byte boundary when the buffer will be flushed.
  348.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  349.  */
  350. static void near
  351. addtobuffer(struct usock *up,int32 code)
  352. {
  353.     if(up->zout->code != -1) {
  354.         /* Insert remaining bits of ZFLUSH codeword */
  355.         up->obuf->data[up->obuf->cnt] = up->zout->code >> up->zout->flushbit;
  356.  
  357.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  358.             up->zout->nextbit = (up->zout->codebits - up->zout->flushbit) % 8;
  359.  
  360.             if(up->zout->nextbit == 0) {
  361.                 ++up->obuf->cnt;
  362.             }
  363.             up->zout->code = -1;
  364.         } else {
  365.             /* not done yet */
  366.             ++up->obuf->cnt;
  367.             up->zout->flushbit += 8;
  368.             addtobuffer(up,code);
  369.             return;
  370.         }
  371.     }
  372.     /* normal codewords are treated here */
  373.     if(up->zout->nextbit == 0) {
  374.         /* we are at a byte boundary */
  375.         if(code == ZFLUSH) {
  376.             up->zout->flushbit = 0;
  377.             up->zout->code = ZFLUSH;
  378.             return;
  379.         }
  380.         up->obuf->data[up->obuf->cnt++] = code;
  381.     } else {
  382.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  383.     }
  384.     if(code == ZFLUSH) {
  385.         /* interrupt here and save the rest of the ZFLUSH
  386.          * codeword for later.
  387.          */
  388.         up->zout->flushbit = 8 - up->zout->nextbit;
  389.         up->zout->code = ZFLUSH;
  390.         return;
  391.     }
  392.     up->obuf->data[up->obuf->cnt] = code >> (8 - up->zout->nextbit);
  393.  
  394.     /* start on a third byte if necessary */
  395.     if(16 - up->zout->nextbit < up->zout->codebits) {
  396.         up->obuf->data[++up->obuf->cnt] = code >> (16 - up->zout->nextbit);
  397.     }
  398.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  399.  
  400.     if(up->zout->nextbit == 0) {
  401.         ++up->obuf->cnt;
  402.     }
  403. }
  404.  
  405. void
  406. lzwflush(struct usock *up)
  407. {
  408.     /* interrupt the encoding process and send the prefix codeword */
  409.     if(up->zout->prefix != -1) {
  410.         addtobuffer(up,up->zout->prefix);
  411.  
  412.         if(up->zout->next + 1 == (int32) (1 << up->zout->codebits)) {
  413.             morebits(up->zout);
  414.         }
  415.         up->zout->prefix = -1;
  416.     }
  417.     /* signal this by sending the ZFLUSH codeword */
  418.     addtobuffer(up,ZFLUSH);
  419. }
  420.  
  421. int
  422. lzwdecode(struct usock *up)
  423. {
  424.     int32 code, data;
  425.  
  426.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf)) == -1) {
  427.         return -1;
  428.     }
  429.     if(up->zin->maxbits == -1) {
  430.         /* receive a recommended value for the maximum no of bits */
  431.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1) {
  432.             return -1;
  433.         }
  434.         if(up->zout->maxbits > up->zin->maxbits) {
  435.             if(up->zout->codebits > up->zin->maxbits) {
  436.                 /* We are already using more bits than our
  437.                  * peer want us to, so clear the encoding
  438.                  * table immediately.
  439.                  */
  440.                 addtobuffer(up,up->zout->prefix);
  441.  
  442.                 if(up->zout->next + 1 == (int32) (1 << up->zout->codebits)) {
  443.                     morebits(up->zout);
  444.                 }
  445.                 addtobuffer(up,ZCC);
  446.                 cleartbl(up->zout);
  447.             }
  448.             up->zout->maxbits = up->zin->maxbits;
  449.         }
  450.     }
  451.     for(;;) {
  452.         if((data = PULLCHAR(&up->zin->buf)) != -1) {
  453.             return (int)data;
  454.         }
  455.         if((code = nextcode(up)) == -1) {
  456.             return -1;
  457.         }
  458.         decodetbl(code,up->zin);
  459.         up->zin->cnt += len_p(up->zin->buf);
  460.         pwait(NULL);                /* TEST */
  461.     }
  462. }
  463.  
  464. static void near
  465. getstring(int32 code,struct lzw *lzw)
  466. {
  467.     for(;;) {
  468.         int i, j;
  469.  
  470.         if(code < ZFLUSH) {
  471.             lzw->buf = pushdown(lzw->buf,1);
  472.             *lzw->buf->data = uchar(code);
  473.             return;
  474.         }
  475.         i = (int)((code - ZFLUSH - 1) / LZWBLK);
  476.         j = (int)((code - ZFLUSH - 1) % LZWBLK);
  477.         lzw->buf = pushdown(lzw->buf,1);
  478.         *lzw->buf->data = lzw->tu.tbl[i][j].data;
  479.         code = (int32) lzw->tu.tbl[i][j].code;
  480.     }
  481. }
  482.  
  483. static char near
  484. firstchar(int32 code,struct lzw *lzw)
  485. {
  486.     for(;;) {
  487.         int i, j;
  488.  
  489.         if(code < ZFLUSH) {
  490.             return uchar(code);
  491.         }
  492.         i = (int)((code - ZFLUSH - 1) / LZWBLK);
  493.         j = (int)((code - ZFLUSH - 1) % LZWBLK);
  494.         code = (int32) lzw->tu.tbl[i][j].code;
  495.     }
  496. }
  497.  
  498. static void near
  499. decodetbl(int32 code,struct lzw *lzw)
  500. {
  501.     unsigned int i,j;
  502.     int32 pagelim;
  503.  
  504.     if(code > lzw->next) {
  505.         tprintf("LZW protocol error, process %s\n",Curproc->name);
  506.         return;
  507.     }
  508.     if(lzw->buf == NULLBUF) {
  509.         lzw->buf = alloc_mbuf(512);
  510.         /* allow us to use pushdown() later */
  511.         lzw->buf->data += lzw->buf->size;
  512.     }
  513.     if(lzw->prefix == -1) {
  514.         getstring(code,lzw);
  515.         lzw->prefix = code;
  516.         return;
  517.     }
  518.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  519.  
  520.     if(lzw->tu.tbl == NULL) {
  521.         lzw->tu.tbl = cxallocw((unsigned)pagelim,sizeof(struct zentry *));
  522.     }
  523.     if(code < ZFLUSH) {
  524.         goto intable;
  525.     }
  526.     i = (unsigned int)((code - ZFLUSH - 1) / LZWBLK);
  527.     j = (unsigned int)((code - ZFLUSH - 1) % LZWBLK);
  528.  
  529.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  530.         lzw->tu.tbl[i] = cxallocw(LZWBLK,sizeof(struct zentry));
  531.         memset(lzw->tu.tbl[i], 0xff,LZWBLK * sizeof(struct zentry));
  532.     }
  533.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  534.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  535.         lzw->tu.tbl[i][j].code = (int16)lzw->prefix;
  536.         getstring(code,lzw);
  537.         lzw->next = code + 1;
  538.         lzw->prefix = code;
  539.  
  540.         if(lzw->next + 1 == (int32) (1 << lzw->codebits)) {
  541.             morebits(lzw);
  542.         }
  543.         return;
  544.     }
  545. intable:
  546.     getstring(code,lzw);
  547.     i = (unsigned int)((lzw->next - ZFLUSH - 1) / LZWBLK);
  548.     j = (unsigned int)((lzw->next - ZFLUSH - 1) % LZWBLK);
  549.  
  550.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  551.         lzw->tu.tbl[i] = cxallocw(LZWBLK,sizeof(struct zentry));
  552.         memset(lzw->tu.tbl[i], 0xff,LZWBLK * sizeof(struct zentry));
  553.     }
  554.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  555.     lzw->tu.tbl[i][j].code = (int16)lzw->prefix;
  556.     lzw->next++;
  557.     lzw->prefix = code;
  558.  
  559.     if(lzw->next + 1 == (int32)(1 << lzw->codebits)) {
  560.         morebits(lzw);
  561.     }
  562. }
  563.  
  564. /* extract the next codeword from the input stream */
  565. static int32 near
  566. nextcode(struct usock *up)
  567. {
  568.     int32 code;
  569.  
  570.     if(up->zin->code == -1) {    /* read the first character */
  571.         if((code = PULLCHAR(&up->ibuf)) == -1) {
  572.             return -1;
  573.         }
  574.         up->zin->code = (code >> up->zin->nextbit);
  575.     }
  576.     if(up->ibuf == NULLBUF)    {    /* next byte is not available yet */
  577.         return -1;
  578.     }
  579.     /* continue assembling the codeword */
  580.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  581.         (8 - up->zin->nextbit)) & (((int32) 1 << up->zin->codebits) - 1);
  582.  
  583.     if((16 - up->zin->nextbit) < up->zin->codebits) {
  584.         PULLCHAR(&up->ibuf);
  585.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  586.         return nextcode(up);
  587.     }
  588.     code = up->zin->code;
  589.     up->zin->code = -1;
  590.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  591.  
  592.     if(up->zin->nextbit == 0) {
  593.         PULLCHAR(&up->ibuf);
  594.     }
  595.     if(code == ZCC) {
  596.         cleartbl(up->zin);
  597.         return nextcode(up);
  598.     }
  599.     if(code == ZFLUSH) {
  600.         up->zin->prefix = -1;
  601.         return nextcode(up);
  602.     }
  603.     return code;
  604. }
  605.  
  606. #endif /* LZW */
  607.